In most real time communication systems, digital signal processing algorithms are implemented using finite precision arithmetic. Data is often mapped from the time domain to the frequency domain using a Fast Fourier Transform (FFT). The FFT is a generic name for a class of computationally efficient computations that implement the Discrete Fourier Transform (DFT) and are widely utilized in digital signal processing. The FFT computation or operation can occur several times during a signal processing portion of a communication system. In signal processing, input signals are a sample of data points that represent amplitude and phase information, which are then reduced to complex numbers that are processed to extract weighted impulse function values. The FFT processing is performed by combinations of complex multiplications and complex additions. Each time FFT computations are performed bit growth can occur, which can compromise signal fidelity if not properly addressed with corrective measures (e.g., scaling).
Many real time communication systems utilize fixed-point digital signal processors (DSPs) to perform the FFT computations. The fixed-point DSP is highly programmable and cost efficient. However, a drawback is that the fixed-point DSP has limited dynamic range, which can be worsened by summation overflow problems that occur in FFT computations. It is common to break a FFT computation into a series of stages when implementing a FFT in a fixed-point processor such as a DSP. The simplest stage is commonly referred to as a Radix-2 stage. A FFT operation can be expressed in terms of only Radix-2 stages by taking advantage of the twiddle factor periodicity. The FFT is simply divided into two smaller FFTs, each of which is then divided into two smaller FFTs. This process is repeated until each FFT operates on only two data values. This simplified FFT can be graphically represented with a Radix-2 butterflies. A FFT consisting of only Radix-2 butterflies contains Log2(N) stages and each stage contains N/2 butterflies, with N being the number of input data values for the FFT operation.
Each Radix-2 butterfly contains two nodes for complex addition and one node for a twiddle factor multiplication. Since each real addition can potentially result in one bit of growth, the input data is scaled so that the result from the addition does not exceed the permissible number of bits. For example, if 16 bits are used to represent data, then the data must first be scaled by ½ so that the result can be represented by a 16-bit value. For each additional Radix-2 stage, an additional scale factor usually is required. In general, a scale factor for 1/Log2(N) is created for a N-point FFT to account for the potential bit growth in all of the associated stages.
However, the employment of FFTs and IFFTs on signals is computationally expensive. Furthermore, many DSPs are not equipped to handle FFT computations in a timely manner to accommodate for other computations being performed on data. In some circumstances, parallel processing has been employed to handle the computations, but generally requires additional system costs and/or system real estate. Therefore, any reduction in computations of a FFT is desirable.